1. Field of the Invention
This invention relates to array processing of neighborhood images, and more particularly relates to table lookup addressing of N.times.N images by addressing larger images through dichotomy windows, that is, through manipulating a multi-bit address into multiple addresses each of fewer bits.
2. Description of the Prior Art
Image processors of the pipeline type are inherently capable of easy segregation of a 3.times.3 neighborhood window, and are inherently fast because no memory access cycle is required during processing. Table lookup in a two-dimensional array normally is very much slower than image processing in a pipelined processor, in a range roughly 1:9, because each pixel of the nine-pixel 3.times.3 neighborhood window requires a memory cycle.
The following publications are representative of the prior art:
U.S. Pat. No. 4,090,174, Van Voorhis, METHOD AND APPARATUS FOR ACCESSING HORIZONTAL SEQUENCES, VERTICAL SEQUENCES AND RECTANGULAR SUBARRAYS FROM AN ARRAY STORED IN A MODIFIED WORD ORGANIZED RANDOM ACCESS MEMORY SYSTEM, May 16, 1978, shows an image processor, for a 2D array, which allows direct access to subarrays without requiring that the desired cluster of bits all fall within the same memory word.
U.S. Pat. No. 4,506,382, Hada et al, APPARATUS FOR DETECTING TWO-DIMENSIONAL PATTERN AND METHOD FOR TRANSFORMING THE PATTERN INTO BINARY IMAGE, Mar. 19, 1985, shows detecting apparatus for comparing a 3.times.3 neighborhood image window on the basis of binary signals stored in a register. This permits the breakdown of a 2D array into the desired 3.times.3 neighborhood windows.
U.S. Pat. No. 4,438,495, Collins et al, TOMOGRAPHY WINDOW-LEVEL GAMMA FUNCTIONS, Mar. 20, 1984, shows window subimage processing using table lookup. There is a memory table of gamma correction values in a first memory. A counter generates a sequence of addresses in a second memory. A variable address generator addresses the first memory to send gamma correction data to the second memory at locations which is corrected.
U.S. Pat. No. 4,534,059, Yamada, METHOD FOR CORRECTING GRADATION OF OUTPUT DATA, FOR USE IN A PICTURE DIGITAL PROCESSING SYSTEM, Aug. 6, 1985, shows multiple lookup table memories used in image processing, operating by using a first lookup table to insert address corrections for accessing a second lookup table.
U.S. Pat. No. 4,541,116, R. M. Lougheed, NEIGHBORHOOD IMAGE PROCESSING FOR IMPLEMENTING FILTERING OPERATIONS, Sept. 10, 1985, shows a technique of reviewing the pixels in a neighborhood image to form a table lookup address to accomplish a transform of the neighborhood image.
Two competing architectures exist for image processing/computer vision; they are the pipelined architecture and the 2D array architecture. For the very important neighborhood operations of image processing/computer vision, the pipelined architecture is superior due to its capability to form a 3.times.3 window then use the window to perform a table lookup. In this respect, the pipelined architecture is 9 times faster than its 2D array counterpart with other factors equivalent.
The table-lookup from a 3.times.3 window can be stated formally as follows:
Given an N.times.N binary image organized as a two-dimensional array of pixels P(s, t) where both s and t run from 0 to N-1, and a table with 512 1-bit entries (entry 0 to entry 511), the output of the table-lookup of a pixel P(i, j) is the content of the table at location TADDR(0:8) where TADDR(0:8) is an integer ranging from 0 to 511 and each TADDR(k) (k from 0 to 8) is a bit to be assigned by the value of a pixel in the 3.times.3 window.
The assignment is as following: TADDR(0)=P(i-1, j-1), TADDR(1)=P(i-1, j), TADDR(2)=P(i-1, j+1), TADDR(3)=P(i, j-1), TADDR(4)=P(i, j), TADDR(5)=P(i, j+1), TADDR(6)=P(i+1, j-1), TADDR(7)=P(i+1, j) and TADDR(8)=P(i+1, j+1) where the i and j indices run from 1 to N-2.
Performing window formulation and the table lookup in one memory cycle is not directly possible for a 2D array, due to the lack of bits required for the window address generation, due to shortage of bandwidth in the communication path, and due to difficulty of the control for the address generation and communication path.
The prior art thus teaches a variety of reasons for manipulating table lookup addresses, and a variety of mechanisms for doing so, but the prior art does not teach nor suggest the invention, which provides an expanded address set to access the memory tables necessary to provide the bits of the desired neighborhood image.